// https://www.lintcode.com/problem/decode-ways/my-submissions

class Solution {
public:
    /**
     * @param s: a string,  encoded message
     * @return: an integer, the number of ways decoding
     */
    int numDecodings(string &s) {
        if (s.empty()) return 0;
        int n = s.length();
        vector<int> res(n + 1, 0);
        res[0] = 1; //初始条件是1，不然不好加；但真的为空返回0
        for (int i = 1; i < n + 1; ++i)
        {
            // if (s[i - 1] > '1' && s[i - 1] < '9') res[i] += res[i - 1]; !!!
            // if (s[i - 1] >= '1' && s[i - 1] <= '9') res[i] += res[i - 1];
            if (s[i - 1] != '0') res[i] += res[i - 1];
            // if (i >= 2 && (s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] >= '1' && s[i - 1] <= '6')))
            // if (i >= 2 && (s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] >= '0' && s[i - 1] <= '6')))
            if (i >= 2 && (s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] <= '6')))
                res[i] += res[i - 2];
        }
        // return s.back(); !!!
        return res.back();
    }
};